import java.util.Arrays;


public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }

        long start = System.currentTimeMillis();
        insertSort(arr);

        long end = System.currentTimeMillis();
        System.out.println(end - start);  //1398  ,插入排序80000个随机数据的数组需要的ms数


    }

    public static int[] insertSort(int arr[]) {
        //第一个数自成一个有序列表,后面的数自成一个无序列表
        //每一次循环后有序列表个数增1,直到循环结束
        //从第二个数开始与前面所有的数相比较
        for (int i = 1; i < arr.length; i++) {
            int insertVal=arr[i];
            int insertIndex=i-1;
            //当要插入的数小于前面的数则代表它要插到这个数之前
            while (insertIndex>=0&&insertVal<arr[insertIndex]){
                //将前面的数后移一位
                arr[insertIndex+1] =arr[insertIndex];
                insertIndex--;
            }
            //当退出while循环后则表明inserIndex=-1或者val大于等于比较的数
            //所以这个数要插入在这个有序列表的头部或者比较索引的后一位
            if (insertIndex!=i-1){
                arr[insertIndex+1]=insertVal;
            }
        }
        return arr;
    }
}
